package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
*   @description https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/
*   @author 曲大人的喵
*   @create 2025/9/19 14:22
*   @since JDK17
*/

public class Solution10 {
    List<Integer>[] g, ans;
    int[] vis;

    void dfs(int cur, int start) {
        vis[cur] = start;
        for (int x : g[cur]) {
            if (vis[x] != start) {
                ans[x].add(start);
                dfs(x, start);
            }
        }
    }
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        vis = new int[n];
        Arrays.fill(vis, -1);
        g = new List[n];
        ans = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        Arrays.setAll(ans, i -> new ArrayList<>());
        for (var edge : edges) {    // 建图
            g[edge[0]].add(edge[1]);
        }

        for (int i = 0; i < n; i++) {
            dfs(i, i);
        }

        return Arrays.asList(ans);
    }
}
